package DataStructuresTest.LinkListTest;

/**
 * 带头结点的双向链表实现
 * MyLinkedList类包含到两端的链、表的大小以及一些方法
 * node类一个节点包含数据以及到前一个节点的链和到下一个节点的链
 * 优点：插入删除花费常数时间，提供addFirst()，removeFirst()，addLast()，removeLast()
 * 缺点：对get调用昂贵
 */
public class MyLinkedList<AnyType> implements Iterable<AnyType> {
    //数据成员
    private int theSize;//LinkList的长度
    private int modCount;
    private Node<AnyType> beginMarker;
    private Node<AnyType> endMarker;

    private static class Node<AnyType>{
        public Node(AnyType d,Node<AnyType> p,Node<AnyType> n){
            data = d;prev = p;next = n;
        }

        public AnyType data;
        public Node<AnyType> prev;
        public Node<AnyType> next;
    }

    public MyLinkedList(){doClear();}

    public void clear(){doClear();}

    public int size(){return theSize;}

    public boolean isEmpty(){return size() == 0;}

    public boolean add(AnyType x){add(size(),x);return true;}
    //重载add方法获取idx
    public void add(int idx,AnyType x){addBefore(getNode(idx,0,size()),x);}

    private void addBefore(Node<AnyType> p, AnyType x){
//        Node<AnyType> newNode = new Node<>(x,p.prev,p);
//        newNode.prev.next = newNode;
//        p.prev = newNode;
        //合并得到
        p.prev = p.prev.next = new Node<>(x,p.prev,p);
        theSize++;
        modCount++;
    }

    public AnyType get(int idx){return getNode(idx).data;}

    public AnyType set(int idx,AnyType newVal){
        Node<AnyType> p = getNode(idx);
        AnyType oldVal = p.data;
        p.data = newVal;
        return oldVal;
    }

    public AnyType remove(int idx){return remove(getNode(idx));}



    /**
     *
     * @param p need to delete
     * @return
     */
    private AnyType remove(Node<AnyType> p){
        p.next.prev = p.prev;
        p.prev.next = p.next;
        theSize--;
        modCount++;
        return p.data;
    }

    /**
     * get the node at position idx,which must range from 0 to size()-1
     * @param idx index to search at
     * @return
     */
    private Node<AnyType> getNode(int idx){return getNode(idx,0,size()-1);}

    /**
     *
     * get the node at position idx,which must range from lower to upper
     * @param idx index to search at
     * @param lower lowest valid index
     * @param upper highest valid index
     * @return
     */
    private Node<AnyType> getNode(int idx,int lower,int upper){
        Node<AnyType> p;
        if (idx < lower || idx > upper)throw new IndexOutOfBoundsException();

        if (idx < size()/2){
            p = beginMarker.next;
            for (int i = 0;i < idx;i++)p = p.next;
        }else {
            p = endMarker;
            for (int i = size(); i > idx; i--) {
                p = p.prev;
            };
        }
        return p;
    }

    private void doClear() {
        //beginMarker为头结点
        beginMarker = new Node<AnyType>(null,null,null);
        endMarker   = new Node<>(null,beginMarker,null);
        beginMarker.next = endMarker;

        theSize = 0;
        modCount++;
    }

    public java.util.Iterator<AnyType> iterator(){
        return new LinkedListIterator();
    }
    private class LinkedListIterator implements java.util.Iterator<AnyType>{
        private Node<AnyType> current = beginMarker.next;
        private int expectedModCount  = modCount;
        private boolean okToRemove = false;

        public boolean hasNext(){return current != endMarker;}

        public AnyType next(){
            if(modCount != expectedModCount)throw new java.util.ConcurrentModificationException();
            if (!hasNext())throw new java.util.NoSuchElementException();

            AnyType nextItem = current.data;
            current = current.next;
            okToRemove = true;
            return nextItem;
        }

        public void remove(){
            if(modCount != expectedModCount)throw new java.util.ConcurrentModificationException();
            if (!okToRemove)throw new IllegalStateException();

            MyLinkedList.this.remove(current.prev);
            expectedModCount++;
            okToRemove = false;
        }
    }
}
